Given a Circular Linked List node, which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.
If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.
If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.
Example 1:
Input: head = [3,4,1], insertVal = 2 Output: [3,4,1,2] Explanation: In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.
Example 2:
Input: head = [], insertVal = 1
Output: [1]
Explanation: The list is empty (given head is null). We create a new single circular list and return the reference to that single node.
Example 3:
Input: head = [1], insertVal = 0 Output: [1,0]
Constraints:
0 <= Number of Nodes <= 5 * 104-106 <= Node.val, insertVal <= 106
Average Rating: 4.83 (60 votes)
Solution
Approach 1: Two-Pointers Iteration
Intuition
As simple as the problem might seem to be, it is actually not trivial to write a solution that covers all cases.
Often the case for the problems with linked list, one could apply the approach of Two-Pointers Iteration, where one uses two pointers as surrogate to traverse the linked list.
One of reasons of having two pointers rather than one is that in singly-linked list one does not have a reference to the precedent node, therefore we keep an additional pointer which points to the precedent node.
For this problem, we iterate through the cyclic list using two pointers, namely
prevandcurr. When we find a suitable place to insert the new value, we insert it between theprevandcurrnodes.
Algorithm
First of all, let us define the skeleton of two-pointers iteration algorithm as follows:
-
As we mentioned in the intuition, we loop over the linked list with two pointers (i.e.
prevandcurr) step by step. The termination condition of the loop is that we get back to the starting point of the two pointers (i.e.prev == head) -
During the loop, at each step, we check if the current place bounded by the two pointers is the right place to insert the new value.
-
If not, we move both pointers one step forwards.
Now, the tricky part of this problem is to sort out different cases that our algorithm should deal with within the loop, and then design a concise logic to handle them sound and properly. Here we break it down into three general cases.
Case 1). The value of new node sits between the minimal and maximal values of the current list. As a result, it should be inserted within the list.
As we can see from the above example, the new value (6) sits between the minimal and maximal values of the list (i.e. 1 and 9). No matter where we start from (in this example we start from the node {3}), the new node would end up being inserted between the nodes {5} and {7}.
The condition is to find the place that meets the constraint of {prev.val <= insertVal <= curr.val}.
Case 2). The value of new node goes beyond the minimal and maximal values of the current list, either less than the minimal value or greater than the maximal value. In either case, the new node should be added right after the tail node (i.e. the node with the maximal value of the list).
Here are the examples with the same input list as in the previous example.
Firstly, we should locate the position of the tail node, by finding a descending order between the adjacent, i.e. the condition of {prev.val > curr.val}, since the nodes are sorted in ascending order, the tail node would have the greatest value of all nodes.
Furthermore, we check if the new value goes beyond the values of tail and head nodes, which are pointed by the prev and curr pointers respectively.
The Case 2.1 corresponds to the condition where the value to be inserted is greater than or equal to the one of tail node, i.e. {insertVal >= prev.val}.
The Case 2.2 corresponds to the condition where the value to be inserted is less than or equal to the head node, i.e. {insertVal <= curr.val}.
Once we locate the tail and head nodes, we basically extend the original list by inserting the value in between the tail and head nodes, i.e. in between the prev and curr pointers, the same operation as in the Case 1.
Case 3). Finally, there is one case that does not fall into any of the above two cases. This is the case where the list contains uniform values.
Though not explicitly stated in the problem description, our sorted list can contain some duplicate values. And in the extreme case, the entire list has only one single unique value.
In this case, we would end up looping through the list and getting back to the starting point.
The followup action is just to add the new node after any node in the list, regardless the value to be inserted. Since we are back to the starting point, we might as well add the new node right after the starting point (our entrance node).
Note that, we cannot skip the iteration though, since we have to iterate through the list to determine if our list contains a single unique value.
The above three cases cover the scenarios within and after our iteration loop. There is however one minor corner case we still need to deal with, where we have an empty list. This, we could easily handle before the loop.
Complexity Analysis
-
Time Complexity: O(N) where N is the size of list. In the worst case, we would iterate through the entire list.
-
Space Complexity: O(1). It is a constant space solution.
November 21, 2019 1:57 AM
hi @algocodehk , it is a good point to mention about the TDD (Test-Driven Development, I suppose). In certain sense, I think TDD does apply to all problems in LeetCode. After all, the online-judge on LeetCode verifies the solutions by running testing cases again each solution.
This problem is not particularly complex or difficult, "algorithmically speaking". If one is asked this problem during the interview, it is a good occasion to show the capability of coming up several diverse test cases. And then It is also critical to work out an "elegant" and "concise" solution that works for all test cases, without resorting to too many conditional branches or loops.
May 24, 2020 2:02 AM
There is no need for two pointers
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
if not head:
head = Node(insertVal)
head.next = head
return head
curr = head
while True:
if curr.val <= insertVal <= curr.next.val:
break
# last element
if curr.val>curr.next.val:
if curr.val <= insertVal >= curr.next.val:
break
elif curr.val >= insertVal <= curr.next.val:
break
curr = curr.next
# all elements are equal
if curr == head:
break
new_node = Node(insertVal)
tmp = curr.next
curr.next = new_node
new_node.next = tmp
return head
November 20, 2019 9:31 PM
to me this problem is an ideal question for a TDD approach, figure out all test cases before coding. Algorithmic wise its only about traversing the list and adding values.
Last Edit: September 23, 2020 4:55 AM
Nice solution. Another more naive yet approachable solution would be to:
- figure out the start and the end of the linked list
- make the linked list temporarily non-circular
- walk the linked list to insert the node at the right position
- restore the circular link
The following is an example:
class Solution {
public Node insert(Node head, int insertVal) {
if (head == null) {
Node nd = new Node(insertVal);
nd.next = nd;
return nd;
}
// Figure out the start and the end of the linked list.
Node start = head.next;
Node end = head;
Node cur = head.next;
while (cur != head) {
if (cur.val > cur.next.val) {
end = cur;
start = cur.next;
break;
}
cur = cur.next;
}
// temporarily make the linked list non-circular
end.next = null;
// loop from start to end to insert at the right position
// then restore the circular link
Node nd = start;
while (nd != null) {
if (nd.next == null) {
nd.next = new Node(insertVal);
nd.next.next = start;
break;
} else if (insertVal >= nd.val && insertVal <= nd.next.val) {
Node next = nd.next;
nd.next = new Node(insertVal);
nd.next.next = next;
end.next = start;
break;
}
nd = nd.next;
}
return head;
}
}
Despite having to do two passes, the time complexity is still ~O(N). The space complexity is ~O(1).
April 28, 2021 2:56 AM
cleaner code, no need to have so many variables. just use a node variable to track where the insertion point is.
public Node insert(Node head, int insertVal) {
if(head == null) {
Node newNode = new Node(insertVal);
newNode.next = newNode;
return newNode;
}
Node node = head;
while(node.next != head) {
if(node.val <= node.next.val) {
if(insertVal >= node.val && insertVal <= node.next.val) {
break;
}
} else {
if(insertVal >= node.val || insertVal <= node.next.val) {
break;
}
}
node = node.next;
}
Node next = node.next;
node.next = new Node(insertVal, next);
return head;
}
September 5, 2020 3:11 AM
well My solution is to find max and min. two pass. stupid me!!!!!!!
August 18, 2020 2:49 AM
Yet another solution that keeps track of the max node to insert the new value. Just feels more natural thinking that way.
class Solution {
public Node insert(Node head, int insertVal) {
// If the list is empty (i.e., given node is null),
// you should create a new single circular list
// and return the reference to that single node.
if (head == null) {
Node insertNode = new Node(insertVal);
// Don't forget to create the circular reference
insertNode.next = insertNode;
return insertNode;
}
Node cur = head;
Node max = head;
// Stop when the insertVal is between cur and its next
while (!(insertVal >= cur.val && insertVal <= cur.next.val)) {
// Keep track of the max node
if (cur.val >= max.val) max = cur;
// Proceed to the next node
cur = cur.next;
// Exit after one full cycle
if (cur == head) break;
}
Node insertNode = new Node(insertVal);
// Insert insertVal in between cur and its next
if (cur != head) {
Node next = cur.next;
cur.next = insertNode;
insertNode.next = next;
// insertVal can't be inserted in between cur and its next.
// insertVal is smaller or bigger than any number in the cycle.
// Insert insertVal after the max node.
} else {
Node next = max.next;
max.next = insertNode;
insertNode.next = next;
}
return head;
}
}
June 2, 2021 8:54 AM
Shouldn't case 1 also cover case 3?
June 1, 2021 11:28 AM
My simple implementation in java:
- handle base case when head is null, return single node circular list
- locate maximum node
- next to max will be min
- delink max and min temporariliy and set current to min
- now problem becomes insert in sorted linked list
- if smallest, then append at head. If largest, append at tail, otherwise just link via previous pointer
- link back max to min to make list circular again.
class Solution {
public Node insert(Node head, int insertVal) {
Node newNode = new Node(insertVal);
if (head == null) {
newNode.next = newNode;
return newNode;
}
Node maxNode = head;
Node cur = head.next;
while (cur != null && cur != head) {
if (cur.val >= maxNode.val) maxNode = cur;
cur = cur.next;
}
Node minNode = maxNode.next;
cur = minNode;
Node prev = null;
maxNode.next = null;
while (cur != null && cur.val < insertVal) {
prev = cur;
cur = cur.next;
}
if (prev == null) {
newNode.next = cur;
minNode = newNode;
}
else if (cur == null) {
maxNode.next = newNode;
maxNode = newNode;
}
else {
prev.next = newNode;
newNode.next = cur;
}
maxNode.next = minNode;
return head;
}
}
May 27, 2021 11:58 PM
how is the following stored in acceding order
Input: head = [3,4,1]
You don't have any submissions yet.
xxxxxxxxxx/*// Definition for a Node.class Node {public: int val; Node* next; Node() {} Node(int _val) { val = _val; next = NULL; } Node(int _val, Node* _next) { val = _val; next = _next; }};*/class Solution {public: Node* insert(Node* head, int insertVal) { }};